package com.study.algorithm.base.list;

import com.google.common.collect.Lists;
import com.study.algorithm.base.common.ListUtil;
import org.apache.commons.collections.CollectionUtils;

import java.util.List;

/**
 * DichotomySearch
 *
 * @author wanghuilong
 * @version 1.0
 * @description dichotomy search
 * @date 2022/11/6 17:15
 */
public class DichotomySearch {

    public static void main(String[] args) {
        List<Integer> list = Lists.newArrayList(1,2,3,4,5,6,7,8,9,10);
        System.out.println(searchForIndex(list,3));
        System.out.println(searchForIndex(list,1));
        System.out.println(searchForIndex(list,10));

        System.out.println(searchForIndex(list,12));

        System.out.println(searchForIndex(list,0));

        //有序重复数组
        list = Lists.newArrayList(2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,5,5,5);

        System.out.println(searchForMostLeftIndex(list,3));

        System.out.println(searchForMostLeftIndex(list,2));

        System.out.println(searchForMostLeftIndex(list,5));


        // 无序数组，相邻数一定不相等  找寻局部最小： i位置上的数，同时小于 i-1 和 i+1 位置上的数字  要求优于O(N)
        list = Lists.newArrayList(1,2,3,4,5,4,3,2,1);

        System.out.println(getLocalMinimumValue(list));

    }


    public static int searchForIndex(List<Integer> list,Integer searchValue) {
        int index = -1;
        if(CollectionUtils.isEmpty(list)) {
            return index;
        }
        boolean isSearched = false;
        index = list.size()/2;
        while (index >= 0 && index < list.size()) {
            int compareToResult = searchValue.compareTo(list.get(index));
            if(compareToResult == 0) {
                 isSearched = true;
                 break;
            }
            //get to the list start ,nothing but return
            if(0 == index) {
                break;
            }

            if(compareToResult == -1) {
                index = index/2;
            }

            if(compareToResult == 1) {
                int value = list.size() - index;
                if(value >= 2) {
                    value = value / 2;
                }
                index = index + value;
            }

        }

        if(Boolean.TRUE.equals(isSearched)) {
            return index;
        }
        return -1;
    }


    public static int searchForMostLeftIndex(List<Integer> list,Integer searchValue) {
        int realIndex = -1;
        if(CollectionUtils.isEmpty(list)) {
            return realIndex;
        }

        boolean isSearched = false;
        int index = list.size()/2;
        while (index >= 0 && index < list.size()) {
            if(index >= realIndex && realIndex != -1) {
                break;
            }

            int compareToResult = searchValue.compareTo(list.get(index));
            if(compareToResult == 0) {
                if(Boolean.FALSE.equals(isSearched)) {
                    isSearched = true;
                }
                if(realIndex == -1) {
                    realIndex = index;
                }
                if(index < realIndex) {
                    realIndex = index;
                }
                index = index/2;
            }
            //get to the list start ,nothing but return
            if(0 == index) {
                break;
            }

            if(compareToResult == -1) {
                index = index/2;
            }

            if(compareToResult == 1) {
                int value = 0;
                if(realIndex == -1) {
                    value = list.size() - index;
                }else {
                    value = realIndex - index;
                }
                if(value >= 2) {
                    value = value / 2;
                }
                index = index + value;
            }

        }

        if(Boolean.TRUE.equals(isSearched)) {
            return index;
        }
        return -1;
    }


    public static int getLocalMinimumValue(List<Integer> list) {
        if(CollectionUtils.isEmpty(list)) {
            return -1;
        }
        //判断开头是否局部最小
        if(list.size() >= 2) {
            if(list.get(0) < list.get(1)) {
                return 0;
            }
        }

        //判断结尾是否局部最小
        if(list.size() >= 2) {
            if(list.get(list.size() - 1) < list.get(list.size() - 2)) {
                return list.size() - 1;
            }
        }

        //如果开头和结尾都不是局部最小  代表开头和结尾的趋势都是向下的趋势，那么在这其中一定至少存在一个局部最小，因为整个数组相邻的数字都不相同
        int index = list.size() / 2;
        while(index > 0 && index < list.size() - 1) {
            if(isLocalMinimumValue(list,index)) {
                return index;
            }
            if(list.get(index) > list.get(index - 1)) {
                index = index / 2;
            }else  if(list.get(index) > list.get(index + 1)) {
                int value = list.size() - index;
                if(value >= 2) {
                    value = value / 2;
                }
                index = index + value;
            }
        }


        return -1;
    }

    private static boolean isLocalMinimumValue(List<Integer> list,int index) {
        if(CollectionUtils.isEmpty(list) || list.size() <= 1) {
            return false;
        }
        if(index == 0 && list.get(0) < list.get(1)) {
            return true;
        }
        if (index == list.size() - 1 && list.get(list.size() - 1) < list.get(list.size() - 2)) {
            return true;
        }
        if(list.get(index-1) > list.get(index)  && list.get(index+1) > list.get(index)) {
            return true;
        }
        return false;
    }

}
